/*
 * @lc app=leetcode.cn id=53 lang=cpp
 *
 * [53] 最大子序和
 */

// @lc code=start
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //这道题之前写过动态规划版本的 试一下贪心怎么写
        //局部最优思想 如果连续和为负 清零 从下一个元素再开始计数
        int res = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            count += nums[i];
            res = max(res, count);
            if (count <= 0)
            {
                count = 0;
            }
        }
        return res;
    }
};
// @lc code=end
